​KDD 2023 | MaskGAE：图自编码器背后的掩码机理

©PaperWeekly 原创 · 作者 | xzjin, jtli

单位 | 中山大学

研究方向 | 图表示学习

2018 年，Bert [1] 的横空出世引领了 NLP 领域的高速发展，通过 Bert 学到的特征在下游任务中取得了非常优异的成绩，在众多公开数据集上获得了 SOTA。体现了 Bert 所利用的代理任务：masked language model（MLM）的强大能力。2021 年，Kaiming 提出的 MAE [2]，通过与 MLM 相似的设计思路，提出了基于 masked image model（MIM）的 MAE，在精度上成功超越了之前占据主流地位的对比学习方法。

masked autoencoding 在文本和图像数据上的成功，也激励了图领域的研究人员：是否可以设计一种新的范式，将 masked autoencoding 应用到非欧数据 graph 上呢？更进一步，如果这样子做获得了成功，那么其背后的机理又是什么？带着这些疑问，我们提出了 maskgae，从理论和实践上对基于掩码的图自编码器进行了探索。

论文题目：

What's Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoders

论文链接：

https://arxiv.org/abs/2205.10053

论文代码：

https://github.com/edisonleeeee/maskgae

背景

在图上做自监督学习往往有两大范式：对比式与生成式。

对比式的方法基于对比学习，通过学习对图的不同增强视图的不变的表示，在各种图表示学习任务中取得了显著成功。尽管图对比方法有效且普遍，但它高度依赖于专门且复杂的代理来进行自监督学习，并且通常需要精心设计的数据增强方法以生成图的不同结构视图。

生成式方法的典型代表是图自编码器（GAE）。其将图输入本身作为自监督并学习重建图结构。与对比方法相比，GAE 通常实现起来非常简单，可以自然地利用图重建作为代理任务，而不需要设计增强视图。但遵循简单的图重构原理的 GAE 可能会过分强调邻近信息，并不总是有利于自监督学习，使其不太适用于链接预测之外的其他具有挑战性的任务。因此，需要为 GAE 设计更好的代理任务。

而 BERT 和 MAE 用到的 MLM 和 MIM 给了我们启发，是否可以设计 masked graph modeling（MGM），促进 GAE 的性能？

动机

2.1 重新审视GAEs

GAEs 采用经典的编码器-解码器框架，该框架旨在通过优化以下二值交叉熵损失，从编码图的低维表示进行解码：

其中 代表经过图编码器生成的节点表示， 代表解码器， ， 分别代表正样本和采样的负样本集合。可以看到，GAEs 通过利用图中相似和不相似节点对作为自监督信号，显示出学习图结构和节点表示的优势。

2.2 GAEs与对比学习之间的联系

在本节分析中，所有理论基础都是基于同态（homophily）图的：如果节点 u 和  之前存在一条边连接，那么它们的底层语义更有可能是相同的。之后从信息论的角度出发，采用对比学习的信息最大化观点（infomax），将 GAEs 与对比学习联系起来：

设 为分别取 和 值的随机变量 𝑋 和 𝑌 之间的互信息（MI）。MI 的另一种重要表征是 Donsker-Varadhan 的变分表示：

critic function 函数 的取值范围是两个参数的可积函数集合，在 gae 的背景下，考虑直接相邻的节点 , 和它们各自对应的 k-hop 子图 ，将相关的联合分布和边缘分布分别记为 ，，，因此，我们可以将公式（1）视为以下基于期望的目标的经验近似：

下面的引理建立了 GAE 和图对比学习之间的联系：

引理 1 指出，最小化 GAEs 目标（公式（1））总体上等同于最大化相邻节点的 𝑘-hop 子图之间的互信息（这里 k 取决于编码器的接受域）。现在假设参数化 𝜔（𝑢，𝑣）对于任意∈H 的近似（𝑢，𝑣）有足够的表达，则由 M-estimation [3] 中的标准结果可知， 的相应经验极小值在概率上收敛于 的最大值。（详细证明见文章附录）

2.3 任务相关信息和GAEs冗余

学习到的 GAEs 表示和对比学习的（渐近）等价并不一定意味着下游任务的良好表现。最近关于对比学习的信息论观点的研究进展 [4]（infomin）表明，要使对比预训练在下游任务中取得成功，需要合理控制任务无关信息。形式上，设 为两个对比视图的随机变量， 为下游任务的目标，将 表示为 和 的条件互信息，我们得到以下简单恒等式：

公式表明，自监督学习想要更好地应用在一个下游任务上时，与该任务相关（task relevant）的信息需要被更好地提取在隐表示中，而与该任务无关（task irrelevant）的信息需要被舍弃。

直观地说，对于某些类型的下游任务信息 ，我们可能期望 在 GAE 公式下较大，因为两个相邻节点的 𝑘-hop 子图共享一个（可能）较大的公共子图。从计算的角度来看，在两个节点的编码阶段，重叠子图的现象可能会影响到 𝑘−1 层的 GNN 消息传递和聚合，从而在表示之间产生很大的相关性，即使编码器与下游任务的相关性很小。为了进一步证明上述推理，给出了在图拓扑与节点特征独立的假设下 的下界：

命题 1：图编码器在 k-layer 的消息传递中产生了许多冗余，而这些 task irrelevant 的冗余信息已经被编码进了邻接节点的隐藏表示中。经过 k-layer 的传播，隐表示中包含了 k-hop 子图的信息，而对于两个邻接节点，k-hop 子图间包含很大的重叠区域。给定节点 ，，它们的重叠子图大小为 ，设重叠子图中最大规模为 ；此外，图中节点的特征都是独立同分布地随机采样自一个  的高斯分布 ，则我们可以给出 task irrelevant 信息的一个下界：

这个下界说明 task irrelevant 的信息和给定两点之间的 k-hop 邻域的重叠程度是正相关的，因此当我们采取基于边的掩码策略时，可以有效地去除 task irrelevant 的冗余信息，从而精简自监督信号，以学习到更好的表征。

方法

3.1 掩码策略

在第 2 部分理论推导中，我们提到经过 k 层 GNN，输出的隐表示包含了 k 跳子图的聚合信息，这部分信息会存在 task irrelevant 的重叠与冗余，因此在掩码策略中，构建了两种掩码途径来减轻冗余。

Edge-wise random masking：使用伯努利分布得到掩码子集，再对原始边集进行随机掩码。

Path-wise random masking：通过预先采样一批节点 ，以它们为源节点进行随机游走，得到一批路径：

路径级掩码打破了节点之间的短期连接，因此强迫模型学习底层语义，来适应被掩蔽的结构。因此，路径级掩码可以更好地利用结构依赖模式，并为更有意义的 MGM 任务捕获高阶连通性。（相对简单的 egde mask，构建的更难的任务）

3.2 编码器

这部分使用了常规的 GCN 作为编码器用来捕获图结构信息，而由于原始图经过掩码后生成了相对稀疏的新子图，为设计一个高效和强大的编码器提供了机会，同时也减轻了预训练大型 gnn 的可扩展性问题。

3.3 解码器

在这部分中设计了两大解码器，第一个是结构解码器：

结构解码器是 GAEs 的一种基本设计，通过计算直连的节点表示间的关系，判断是否可以聚合为连边来进行解码

第二个是度解码器，作为辅助模型来平衡连通性和结构信息。

由于图结构本身具有比边连接更多的丰富的监督信号，我们可以强制模型近似掩码图中的节点度，以方便训练。将度解码器定义为：

3.4 学习目标

MaskGAE 的损失由两个部分组成：

(i) Reconstruction loss：Reconstruction loss 衡量模型在边级别重建掩码图的效果，其形式类似于 Eq.(1)

(ii) Regression loss：Regression loss 衡量的是节点度预测与掩码图中原始节点度的匹配程度。我们根据节点级别计算近似度与原始度之间的均方误差（MSE）：

可以视作是编码器的正则化器来学习更一般化的表示。

最终，我们需要最小化的损失函数如下：

▲ 图2：MaskGAE框架概述，使用非对称编码器-解码器设计执行掩码图建模

3.5 掩码策略以减轻子图重叠

考虑 - 之间的连边，以 和  为中心的子图在消息传播期间形成两个相反的视图。然而，配对子图视图之间在节点和边方面存在很大的重叠，这可能会阻碍 GAE 的对比学习。相反，在 - 上有掩蔽的 MaskGAE 可以避免一个较大的重叠子图，从而有利于 GAEs 的对比方案。

▲ 图3：体现 masking and predicting 优越性的说明示例。在正样本连边上通过mask策略，显著减少了两个配对子图视图的冗余

在定量分析上，根据节点和边计算所有成对子图的平均重叠，分别表示为 和 ，使用如下的计算公式计算得到表 1：

▲ 表1：子图重叠统计（%）

通过掩码策略， 和 都显着降低了。值得注意的是，Tpath 在减少子图重叠方面表现出比 Tedge 更好的能力，这一点可以从两个数据集上始终较低的 和 得到证明。总的来说，结果证明了采用掩码策略对 GAEs 的好处（路径掩码表现更出色）。在实验部分我们也得到了相同的结论。

实验

在实验部分，下游任务主要是节点分类和链路预测，共在 8 个公开数据集上完成了实验。

▲ 表2：数据集的统计数据

▲ 表3：链路预测实验结果

▲ 表4：节点分类实验结果

可以看到，在节点分类和链路预测这两大任务上，MaskGAE 均展示了优越性能。

不同掩码比例以不同的方式控制 Tedge 和 Tpath 中掩蔽子图的的大小，图4展示了不同掩码比例对节点分类任务性能的影响。可以看到，掩码策略确实对下游性能产生了显著的性能改进。特别是当采用较大的掩码比时，MaskGAE 的性能得到了平稳的提高，这验证了原始图存在的信息冗余，也与我们的理论证明 MGM 改进了自监督学习方案相一致。

▲ 图4：不同掩码比例对节点分类任务性能的影响

图 5 说明了适当比例度解码损失有助于学习下游任务的良好表示。但也可能会过度拟合结构信息从而导致性能下降。

▲ 图5：度解码损失对对节点分类任务性能的影响

图 6 显示了不同嵌入维度的影响。嵌入大小对图表示学习非常重要，它反映了信息压缩的有效性。对于 MaskGAE 来说，较小的嵌入尺寸（大多数情况下为 64）就足够了。

▲ 图6：嵌入维度对节点分类任务性能的影响

表 5 显示了编码器结构的影响。可以看到，使用 GCN 作为编码器的 MaskGAE 在所有情况下都比 GAT 和 SAGE 表现出显著的性能提高，这表明在 MGM 的帮助下一个简单的编码器（GCN）足以学习有用的表示。

结论

在这项工作中，我们对掩码图建模（MGM）进行了全面的研究，并提出了 MaskGAE，一个基于理论的自监督学习框架。通过将 MGM 作为代理任务。MaskGAE 对自监督学习下的 GAEs，进行了理论上的解释：

(i) GAEs 本质上是对比学习模型，最大化与链接边相关的配对子图视图之间的互信息;

(ii) MGM 可以受益于互信息最大化，因为掩码策略显著减少了两个子图视图之间的重叠（冗余）。特别地，文章还提出了一种路径掩码策略来促进 MGM 任务的性能。在实验中，MaskGAE 表现出比 GAEs 显著提高的性能，并且在链路预测和节点分类基准上的性能与强基线相当或更好。

参考文献

[1] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL-HLT (1). Association for Computational Linguistics, 4171–4186.

[2] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross B. Girshick. 2022. Masked Autoencoders Are Scalable Vision Learners. In CVPR. IEEE, 15979–15988.

[3] Aad W Van der Vaart. 2000. Asymptotic statistics. Vol. 3. Cambridge university press

[4] Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. 2020. What Makes for Good Views for Contrastive Learning?. In NeurIPS, Vol. 33. 6827–6839.

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·

·